1. Technical Field
The present disclosure relates to techniques for obtaining data for display from a data set at a resolution appropriate for visualization, including, in one embodiment, techniques for obtaining data from a multi-resolution data set descriptive of a three-dimensional surface, such as a digital terrain model (DTM), at a resolution appropriate for visualization.
2. Background Information
Often a three-dimensional surface may be represented by a data set that describes its topography. Such a data set may be constructed from punctual measurements that describe a height of the surface at discrete points. For example, where the three-dimensional surface is terrain, a digital terrain model (DTM) may be used to represent the topography of the terrain. Such a DTM may be constructed from punctual elevation measurements of the terrain that describe elevation at discrete points. Some DTMs may include data descriptive of the ground's surface as well as above-ground objects (e.g., buildings, bridges, cars, trees, etc.). Other DTMs may only include data descriptive of the ground's surface, and exclude above-ground objects. The punctual elevation measurements used to create a DTM may be obtained via any of a variety of surveying and measurement techniques. For example, Light Detection and Ranging (LIDAR), stereo photogrammetry from aerial surveys, real time kinematic global positioning, as well as other surveying and measurement techniques may be used in creation of a DTM.
A data set that describes the topography of three-dimensional surface, such as a DTM that describes the topology of terrain, may be stored using a variety of data structures. One popular data structure for storing a data set, such as a DTM, is a raster. In contrast to rasters used in raster graphics, where each position in a matrix typically includes a color measurement for a corresponding pixel in an image, in a raster used with a DTM, positions in a matrix typically include an elevation measurement for a corresponding point in the terrain. Such a raster may be small (e.g., include elevation measurements for only a few thousand points) or large (e.g., include elevations measurements for billions of points). Indeed, large DTMs have become increasingly prevalent due to advances in the surveying and measurement techniques used to collect the underlying punctual elevation measurements.
A data set that describes the topography of a three-dimensional surface may be used for a variety of different purposes. For example, a DTM that describes the topology of terrain may be used for water flow analysis, volume calculations, realistic three-dimensional visualization, artistic presentation, as well as a variety of other purposes. Many of the uses, however, require the data set (e.g., DTM) to be represented as a solid surface, rather than as a series of discreet points. As such, a data set (e.g. DTM) that is stored as a raster may be triangulated so that, instead of being represented as a series of discrete points, it is represented in as a triangle mesh, the triangles interconnected to each other to form a solid surface. A DTM that is represented as a triangle mesh is referred to herein as a “triangulated DTM.” FIG. 1 is an illustration of an example triangulated DTM 100 (the DTM data courtesy of Ville De Québec).
A user will often desire to view a portion of a data set that describes the topography of a three-dimensional surface (e.g., a DTM) on a display screen of an electronic device using a computer aided design (CAD) application or other software. Typically, the CAD application interprets the information in the data set as simple geometry and sends all such geometry for the view to be displayed to a graphics subsystem for rendering. This simple geometry is converted by the graphics subsystem into pixels for display on the display screen. However, problems develop when the number of points in the geometry approaches the number of pixels (i.e., the screen resolution) of the display screen. For example, should a user try to view a portion of a triangulated DTM that contains 920918 points, on a screen that has a resolution of 1,310,720 pixel (1280 pixels by 1024 pixels), so many points may be loaded that the resulting image appears almost completely solid (e.g., white). That is, the CAD application may be attempting to display so much data that, given the screen resolution, the resulting image becomes almost entirely useless.
The task of creating a meaningful display from a data set that describes the topography of a three-dimensional surface (e.g. a DTM) may be complicated by a variety of factors. Very large data sets may be arranged into various “levels of detail”, such that there are multiple representations of data at various resolutions. A data set that describes the topography of a three-dimensional surface with multiple representations of data at various resolutions is referred to herein as a “multi-resolution data set”, and, more specifically, a DTM that describes the topography of terrain with multiple representations of data at various resolutions is referred to herein a “multi-resolution DTM”. The data of a multi-resolution data set (e.g., a multi-resolution DTM) may be represented two-and-a-half-dimensionally (i.e., in 2.5D) where there is a unique Z-axis value for a given X/Y location).
Further complicating issues, the data of a data set that describes the topography of a three-dimensional surface (e.g., a DTM) may be non-uniformly distributed over the area represented and may have a non-uniform density. Still further, the data may have an irregular (e.g., non-rectangular) shape. These and other issues make meaningful display from a data set even more complicated.
What is needed is an improved technique for obtaining data from a data set that describes the topography of a three-dimensional surface (e.g., a DTM) at a resolution appropriate for visualization.